package com.captain.special.二叉树.中等;

import com.captain.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/20 15:39
 */
public class 删除二叉搜索树中的节点450 {

    public static void main(String[] args) {
        TreeNode node = TreeNode.spanningTree(new Integer[]{5, 3, 6, 2, 4, null, 7});
        new 删除二叉搜索树中的节点450().deleteNode(node, 7);
    }

    boolean find = false;
    List<Integer> ans;
    TreeNode parentNode = null;
    TreeNode curNode = null;
    Integer target = 0;

    public TreeNode deleteNode(TreeNode root, int key) {
        ans = new ArrayList<>();
        target = key;
        minRecur(root, null);
        if (parentNode == null && curNode == null) {
            return root;
        }
        if (parentNode == null) {
            recur(root);
            ans.remove(target);
            return build(0, ans.size() - 1);
        } else if (parentNode.left != null && parentNode.left.equals(curNode)) {
            recur(parentNode.left);
            ans.remove(target);
            parentNode.left = build(0, ans.size() - 1);
        } else if (parentNode.right != null && parentNode.right.equals(curNode)) {
            recur(parentNode.right);
            ans.remove(target);
            parentNode.right = build(0, ans.size() - 1);
        }
        return root;

    }

    public TreeNode build(int left, int right) {
        if (left > right) return null;
        int mid = (right - left) / 2 + left;
        TreeNode node = new TreeNode(ans.get(mid));
        node.left = build(left, mid - 1);
        node.right = build(mid + 1, right);
        return node;
    }

    public void recur(TreeNode node) {
        if (node == null) {
            return;
        }
        recur(node.left);
        ans.add(node.val);
        recur(node.right);
    }

    public void minRecur(TreeNode node, TreeNode parent) {
        if (node == null) {
            return;
        }
        if (find) {
            return;
        }
        minRecur(node.left, node);
        if (node.val.equals(target)) {
            find = true;
            parentNode = parent;
            curNode = node;
        }
        minRecur(node.right, node);
    }
}
